﻿#define _CRT_SECURE_NO_WARNINGS 1


// 逆向思维
// 从出口开始算

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int solution(int N, int M, vector<vector<char>> data)
{
    int exitX = -1, exitY = -1;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (data[i][j] == 'O')
            {
                exitX = i;
                exitY = j;
                break;
            }
        }
        if (exitX != -1) break;
    }
    if (exitX == -1) return 0;

    vector<vector<bool>> reachable(N, vector<bool>(M, false));
    queue<pair<int, int>> q;
    q.push({ exitX, exitY });
    reachable[exitX][exitY] = true;

    int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    char expected[4] = { 'D', 'U', 'R', 'L' };

    while (!q.empty())
    {
        auto front = q.front();
        q.pop();

        int x = front.first, y = front.second;

        for (int i = 0; i < 4; ++i) {
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];

            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if (data[nx][ny] == expected[i] && !reachable[nx][ny]) {
                    reachable[nx][ny] = true;
                    q.push({ nx, ny });
                }

                if (data[nx][ny] == '.' && !reachable[nx][ny]) {
                    reachable[nx][ny] = true;
                    q.push({ nx, ny });
                }
            }
        }
    }

    int dangerous = 0;
    for (auto& row : reachable) {
        for (bool val : row) {
            if (!val) dangerous++;
        }
    }
    return dangerous;
}


int main()
{
    // Add your test cases here
    std::vector<std::vector<char>> pattern = {
        {'.', '.', '.', '.', '.'},
        {'.', 'R', 'R', 'D', '.'},
        {'.', 'U', '.', 'D', 'R'},
        {'.', 'U', 'L', 'L', '.'},
        {'.', '.', '.', '.', 'O'}
    };

    std::cout << (solution(5, 5, pattern) == 10) << std::endl;

    return 0;
}